L2-026 小字辈

题目 L2-026 小字辈

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

priority_queue<int> pq;

multiset<int> s;

vector<vector<int>> g;

int maxDeep=-inf;

vector<int> ans;

void dfs(int u,int deep){

	if(deep>=maxDeep){

		if(deep>maxDeep){

			ans.clear();

			maxDeep=deep;

			ans.push_back(u);

		}

		else if(deep==maxDeep){

			ans.push_back(u);

		}

	}

	for(auto nx:g[u]){

		dfs(nx,deep+1);

	}

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	g.resize(n+1);

	vector<int> roots;

	for(int i=1;i<=n;i++){

		int fa;cin>>fa;

		if(fa==-1)	roots.push_back(i);

		else g[fa].push_back(i);

	}

	for(auto r:roots)	dfs(r, 1);

	cout<<maxDeep<<endl;

	bool isFirst=true;

	for(auto v:ans)	 {

		if(!isFirst)	cout<<" ";

		cout<<v;

		isFirst=false;

	}

	return 0;

}

同类题型

视频讲解

⬅️ L2-025 分而治之 🏠 00-天梯赛 ➡️ L2-027 名人堂与代金券